package practice;

import java.util.Scanner;



// 创建并中序遍历二叉树：
// 该题给定了空树位置，所以是唯一的树！！
// 依据前序遍历结果创建二叉树，然后进行中序遍历并输出
public class CreateTravel {
    // 定义节点类为内部类
    static class TreeNode {
        TreeNode left;
        TreeNode right;
        char val;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    // 创建二叉树的方法：createTree
    public int i =0; // 不建议定义静态成员变量：因为可能会有多个用例会有变量i
    public TreeNode createTree(String s) {
        // 如果不是空 就创建结点
        // 前序遍历：先根结点，然后左子树（又按照根-左-右），右子树（根-左-右）
        // 使用i进行遍历
        TreeNode root = null;
        if(s.charAt(i) != '#') {
            // 创建根结点
            root = new TreeNode(s.charAt(i));
            i++;
            // 进行左右子树的创建
            root.left = createTree(s); // 注意此处进行递归是要改变i值的，所以i放到外面
            root.right = createTree(s);
        } else {
            // 跳过
            i++;
        }
        return root;
    }
    // 进行中序遍历:左 根 右 -- 递归
    public void inOrder(TreeNode root) {
        if(root==null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextLine()) {
            String s = scanner.nextLine();
            CreateTravel createTravel = new CreateTravel();
            TreeNode root = createTravel.createTree(s);
            createTravel.inOrder(root);
        }
    }
}
